"""
给你一个整数 n，请你帮忙统计一下我们可以按下述规则形成多少个长度为 n 的字符串：

字符串中的每个字符都应当是小写元音字母（'a', 'e', 'i', 'o', 'u'）
每个元音 'a' 后面都只能跟着 'e'
每个元音 'e' 后面只能跟着 'a' 或者是 'i'
每个元音 'i' 后面 不能 再跟着另一个 'i'
每个元音 'o' 后面只能跟着 'i' 或者是 'u'
每个元音 'u' 后面只能跟着 'a'
由于答案可能会很大，所以请你返回 模 10^9 + 7 之后的结果。

 

示例 1：

输入：n = 1
输出：5
解释：所有可能的字符串分别是："a", "e", "i" , "o" 和 "u"。
示例 2：

输入：n = 2
输出：10
解释：所有可能的字符串分别是："ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" 和 "ua"。
示例 3：

输入：n = 5
输出：68

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-vowels-permutation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

"""
class Solution(object):

    def countVowelPermutation(self, n):
        """
        :type n: int
        :rtype: int
        """

        if n==0:
            return 0
        def sonCountVowelPermutation( item, n):

            if n == 1:
                return 1
            if item == "a":
                return sonCountVowelPermutation("e", n - 1)

            elif item == "e":
                return sonCountVowelPermutation("a", n - 1)+sonCountVowelPermutation("i", n - 1)

            elif item == "i":
                return sonCountVowelPermutation("a", n - 1)+ sonCountVowelPermutation("e", n - 1)+sonCountVowelPermutation("o", n - 1)+sonCountVowelPermutation("u", n - 1)
            elif item == "o":
                return sonCountVowelPermutation("i", n - 1)+sonCountVowelPermutation("u", n - 1)
            elif item == "u":
                return sonCountVowelPermutation("a", n - 1)
        return sonCountVowelPermutation("a", n) + sonCountVowelPermutation("e", n)  + sonCountVowelPermutation("i", n ) + sonCountVowelPermutation("o", n )+sonCountVowelPermutation("u", n )
"""
线性 DP
定义 f[i][j]f[i][j] 为考虑长度为 i + 1i+1 的字符串，且结尾元素为 jj 的方案数（其中 jj 代表数组 ['a', 'e', 'i', 'o', 'u'] 下标）。

不失一般性考虑 f[i][j]f[i][j] 该如何计算。

我们可以从题意给定的规则进行出发，从 f[i]f[i] 出发往前更新 f[i + 1]f[i+1]，也可以直接利用对称性进行反向分析。

为了方便大家理解，还是将常规的「从 f[i]f[i] 出发往前更新 f[i + 1]f[i+1]」作为主要分析方法吧。

根据条件可以容易写出转移方程：

每个元音 'a' 后面都只能跟着 'e' ：   f[i + 1][1] += f[i][0]    f[i+1][1]+=f[i][0]；
每个元音'e'后面只能跟着'a'或者是'i' ：f[i + 1][0] += f[i][1]    f[i+1][0]+=f[i][1]     f[i + 1][2] += f[i][1]f[i+1][2]+=f[i][1]；
每个元音'i'后面不能 再跟着另一个'i' ：f[i + 1][j] += f[i][2], (j 不能为 2)               f[i+1][j]+=f[i][2],(j不能为2)；
每个元音'o'后面只能跟着'i'或者是'u' ：f[i + 1][2] += f[i][3]    f[i+1][2]+=f[i][3]      f[i + 1][4] += f[i][3]  f[i+1][4]+=f[i][3]；
每个元音'u'后面只能跟着'a' ：        f[i + 1][0] += f[i][4]    f[i+1][0]+=f[i][4]

"""
MOD = int(1e9) + 7
class Solution:
    def countVowelPermutation(self, n: int) -> int:
        f = [[1] * 5] + [[0] * 5 for _ in range(n - 1)]
        for i in range(1, n):
            f[i][0] = f[i-1][1]
            f[i][1] = (f[i-1][0] + f[i-1][2]) % MOD
            f[i][2] = ((((f[i-1][0] + f[i-1][1]) % MOD + f[i-1][3]) % MOD) + f[i-1][4]) % MOD
            f[i][3] = (f[i-1][2] + f[i-1][4]) % MOD
            f[i][4] = f[i-1][0]
        return (((((f[-1][0] + f[-1][1]) % MOD + f[-1][2]) % MOD + f[-1][3]) % MOD) + f[-1][4]) % MOD
"""
矩阵快速幂
"""
import numpy as np
MOD = 10 ** 9 + 7
dtype = np.dtype('uint64')
class Solution:
    def countVowelPermutation(self, n: int) -> int:
        ans, mat = np.ones(5, dtype=dtype), np.array(
            [  [0, 1, 1, 0, 1]
                , [1, 0, 1, 0, 0]
                , [0, 1, 0, 1, 0]
                , [0, 0, 1, 0, 0]
                , [0, 0, 1, 1, 0] ]
            , dtype=dtype)
        n -= 1
        while n:
            if n & 1:
                ans = ans @ mat % MOD
            mat = mat @ mat % MOD
            n >>= 1
        return int(ans.sum()) % MOD
'''
定义a,e,i,o,u分别为以该字母结尾的序列的个数，然后遍历n-1次，每次都更新这五个变量的值

更新的规则在于，目前长度为n的以a结尾的序列，是由长度为n-1的由e,u和i结尾的序列增加一个a得到的，所以a = e + u + i

以此类推可得另外五个的

*在每轮更新的时候都取模，比更新完再取模速度快很多
'''
class Solution:
    def countVowelPermutation(self, n: int) -> int:
        a, e, i, o, u, M = 1, 1, 1, 1, 1, 10 ** 9 + 7
        for _ in range(n - 1):
            a, e, i, o, u = (e + u + i) % M, (a + i) % M, (e + o) % M, i % M, (o + i) % M
        return sum([a, e, i, o, u]) % M